import org.junit.jupiter.api.DisplayName;
import org.junit.jupiter.params.ParameterizedTest;
import org.junit.jupiter.params.provider.Arguments;
import org.junit.jupiter.params.provider.MethodSource;

import java.util.HashSet;
import java.util.Set;
import java.util.stream.Stream;

/**
 * 最长连续序列
 * 题目：给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度,您的算法应以O(n)复杂性运行。
 * <p>
 * 示例 1：
 * 输入：nums = [100,4,200,1,3,2]
 * 输出：4
 * 解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。
 * <p>
 * 示例 2：
 * 输入：nums = [0,3,7,2,5,8,4,6,0,1]
 * 输出：9
 * <p>
 * 来源：力扣（LeetCode-128）
 * 链接：https://leetcode-cn.com/problems/longest-consecutive-sequence
 *
 * @author godfrey
 * @since 2020-11-02
 */
@DisplayName("最长连续序列")
public class LongestConsecutive extends BaseTest {

    static Stream<Arguments> testArguments() {
        return Stream.of(
                Arguments.arguments((Object) new int[]{100, 4, 200, 1, 3, 2}),
                Arguments.arguments((Object) new int[]{0, 3, 7, 2, 5, 8, 4, 6, 0, 1})
        );
    }

    @DisplayName("哈希表-时间复杂度O(n)，空间复杂度O(n)")
    @ParameterizedTest
    @MethodSource("testArguments")
    void longestConsecutive(int[] nums) {
        if (nums.length < 2) {
            System.out.println(nums.length);
        }
        final Set<Integer> mySet = new HashSet<>();
        for (int num : nums) {
            mySet.add(num);
        }
        int longest = 0;
        for (int num : nums) {
            int length = 1;
            for (int i = num - 1; mySet.contains(i); --i) {
                mySet.remove(i);
                ++length;
            }
            for (int i = num + 1; mySet.contains(i); ++i) {
                mySet.remove(i);
                ++length;
            }
            longest = Math.max(longest, length);
        }
        System.out.println(longest);
    }
}
